#pragma once
#include "LinkNode.h"
template<typename T>
class quickSort
{
private:
	T* array;
	int size;
public:
	quickSort(T* a,int n) :array(a),size(n){}
	int partion(int low, int high);					//划分
	int getSize();									//获取大小
	T* getArray();									//获取数组
	void qsort(int low, int high);					//快排
	void print();									
	static void qSort(LinkNode<T>* low, LinkNode<T>* high);	//链表快排
};
// 获取大小
template<typename T>
int quickSort<T>::getSize() {
	return this->size;
}
// 获取数组
template<typename T>
T* quickSort<T>::getArray(){
	return this->array;
}
// 划分
template<typename T>
int quickSort<T>::partion(int low, int high) {
	T privote = array[low];
	int i = low;
	int j = high;
	while (i < j) {
		while (i<j && array[j] >= privote)j--;
		array[i] = array[j];
		while (i<j && array[i] <= privote)i++;
		array[j] = array[i];
	}
	array[i] = privote;
	return i;
}
// 快排
template<typename T>
void quickSort<T>::qsort(int low, int high) {
	if (low < high) {
		int privote = partion(low, high);
		qsort( low, privote - 1);
		qsort( privote + 1, high);
	}
}
// 链表快排
template<typename T>
void quickSort<T>::qSort(LinkNode<T>* low,LinkNode<T>* high) {
	if (low == nullptr || low == high)	return;
	T elem;
	LinkNode<T>* p = low->next;
	LinkNode<T>* small = low;
	while (p != high) {
		if (p->element <= low->element) {
			small = small->next;
			elem = small->element;
			small->element = p->element;
			p->element = elem;
		}
		p = p->next;
	}
	elem = low->element;
	low->element = small->element;
	small->element = elem;
	qSort(low, small);
	qSort(small->next, high);
}
// 打印
template<typename T>
void quickSort<T>::print() {
	for (int i = 1; i <= this->getSize(); i++) {
		cout << this->array[i] << " ";
	}
}